1. Field of the Invention
This invention relates to methods for eliminating spatial artifacts in digital imaging, more particularly to a method for applying an aperiodic, halftone, tiling scheme to digital images.
2. Background of the Invention
Digital images are typically reproduced using a grid of elements, such as in dots or picture elements (pixels). Due to the periodic nature of these grids, spatial artifacts can occur in the resulting image. For example, images such as those in digital printing may have an artifact referred to as Moirxc3xa9 patterns.
These patterns are formed when two periodic and nearly identical spatial frequencies interfere, much like the interference patterns caused by two disturbances in a body of water. In some areas the xe2x80x98ripplesxe2x80x99 sum together, in others they subtract. When these sum and difference artifacts appear in spatial frequencies perceptible to the human eye, they are perceived and detract from the image quality. In displayed or printed images, these patterns may occur because of the sampling frequency of the input device beats against the halftone frequency of the original image.
Several different approaches have been used to overcome this problem. One approach is to apply a random noise pattern to the pixels of the image to break up the interference patterns. The random noise pattern is often generated using blue noise. One example of such an approach is shown in U.S. Pat. No. 5,557,709, issued Sep. 17, 1996.
Other approaches process the colors of a printed image to render one color in a non-periodic fashion. This serves to break up the interference patterns. An example of such an approach is shown in U.S. Pat. No. 5,740,334, issued Apr. 14, 1998.
The use of quasiperiodic tools is also shown by U.S. Pat. No. 5,379,118, issued Jan. 3, 1995. In this approach, the frequencies of the appearance of the elements of a picture are manipulated. The pattern is quasiperiodic in this application, however, as the pattern does achieve symmetry after a number of elements are produced.
One unique aperiodic but non-random pattern is Ammann tiles, named after Robert Ammann, one of the discoverers of these tiles. These tiles and other aperiodic tiling schemes have base tiles, or proto-tiles, that are then used to build larger tiles that have the same aperiodic properties of the base tiles. Aperiodic as used in this disclosure refers to non-periodic but non-random patterns, unlike those discussed above. No use of these types of patterns has been made in digital imaging applications, even though their aperiodicity would be useful in these applications. The applications of non-periodic patterns in the above approaches manipulate the sampling and pixel frequencies pixel by pixel not on an image basis. Applying aperiodicities at the image level has certain advantages.
Therefore, a method and structure applying aperiodic tiles to digital images is needed.
One aspect of the invention is a method for applying aperiodicity to image data to mitigate spatial artifacts. The method comprises the steps of receiving image data in a periodic format and converting it to an aperiodic format. Alternatively, the method comprises the steps of receiving data in an aperiodic format and converting it to a periodic format. One example of an aperiodicity that can be used for formatting the data is Ammann tiling.
Another aspect of the invention is a system that has an aperiodic input device and an aperiodic output device. The input device produces aperiodic image data and passes it to the aperiodic output device for rendering.